package com.shr.code_interview;

import java.util.ArrayList;

public class Solution_40 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>() ;
        if(input != null && input.length > 0 && k <= input.length && k > 0){
        	int pos = partition(input, 0, input.length - 1);
        	while(pos != k-1){
        		if(pos < k-1)
        			pos = partition(input, pos + 1, input.length - 1) ;
        		else
        			pos = partition(input, 0, pos - 1);
        	}
        	
        	for(int i = 0;i<k;i++)
        		list.add(input[i]) ;
        }
        return list ;
    }

	private int partition(int[] input, int low, int up) {
		int key = input[low] ;
		while(low < up){
			while(input[up] >= key && low < up) up--;
			input[low] = input[up] ;
			while(input[low] <= key && low < up) low++ ;
			input[up] = input[low] ;
		}
		input[low] = key;
		return low;
	}	
}
